class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null
  }

  createNode(key) {
    return new Node(key)
  }

  // 插入
  insert(key) {
    const node = this.createNode(key)
    let current = this.root
    let parent = this.root
    // 如果root为空，root则为插入的节点
    if (this.root === null) {
      this.root = node
      return
    }
    while (current !== null) {
      parent = current
      if (current.key < key) {
        current = current.right
      } else {
        current = current.left
      }
    }
    if (parent.key > key) {
      parent.left = node
    } else {
      parent.right = node
    }
  }

  // 先序遍历
  preOrderTraversal(handler) {
    this.preOrderTraversalNode(this.root, handler)
  }

  preOrderTraversalNode(node, handler) {
    if (node !== null) {
      handler(node)
      // 遍历左子树
      this.preOrderTraversalNode(node.left, handler)
      // 遍历右子树
      this.preOrderTraversalNode(node.right, handler)
    }
  }

  // 中序遍历
  midOrderTraversal(handler) {
    this.midOrderTraversalNode(this.root, handler)
  }

  midOrderTraversalNode(node, handler) {
    if (node !== null) {
      // 遍历左子树
      this.midOrderTraversalNode(node.left, handler)
      handler(node)
      // 遍历右子树
      this.midOrderTraversalNode(node.right, handler)
    }
  }

  // 后续遍历
  postOrderTraversal(handler) {
    this.postOrderTraversalNode(this.root, handler)
  }

  postOrderTraversalNode(node, handler) {
    if (node !== null) {
      // 遍历左子树
      this.postOrderTraversalNode(node.left, handler)

      // 遍历右子树
      this.postOrderTraversalNode(node.right, handler)

      handler(node)
    }
  }

  // 寻找最大值
  max() {
    let current = this.root
    let node

    while (current !== null) {
      node = current
      current = current.right
    }

    return node.key
  }

  // 寻找最小值
  min() {
    let current = this.root
    let node

    while (current !== null) {
      node = current
      current = current.left
    }

    return node.key
  }

  // 寻找对应key的node
  search(key) {
    let current = this.root

    while (current !== null) {
      if (current.key === key) {
        return current
      } else if (current.key > key) {
        current = current.left
      } else {
        current = current.right
      }
    }

    return false
  }

  // 删除通过前驱
  removeByPrecursor(key) {
    let parent = this.root
    let current = this.root
    let isLeftNode = false

    while (current.key !== key) {
      parent = current

      if (current.key > key) {
        isLeftNode = true
        current = current.left
      } else {
        isLeftNode = false
        current = current.right
      }
      // 没有找到要删除的
      if (current === null) return false
    }

    // 删除的是叶子节点
    if (current.left === null && current.right === null) {
      if (isLeftNode) {
        parent.left = null
      } else {
        parent.right = null
      }
    }
    // 删除的节点有一个左节点
    else if (current.right === null) {
      if (isLeftNode) {
        parent.left = current.left
      } else {
        parent.right = current.right
      }
    }
    // 删除的节点有一个右节点
    else if (current.left === null) {
      if (isLeftNode) {
        parent.left = current.right
      } else {
        parent.right = current.right
      }
    }
    // 删除的节点有两个子节点
    else {
      const precursor = this.getPrecursor(current)

      if (isLeftNode) {
        parent.left = precursor
      } else {
        parent.right = precursor
      }
      // 将前驱节点的右节点连接到删除节点的右节点，确保被删除节点的右节点不会断
      precursor.right = current.right
    }
  }

  getPrecursor(delNode) {
    let parent = delNode
    let current = delNode.left
    let node = delNode

    while (current !== null) {
      parent = node
      node = current
      current = current.right
    }

    if (delNode.left !== node) {
      // 如果删除的节点的左节点不等于前驱，将前驱节点的左节点交给前驱节点的父节点保管，确保前驱节点的左节点不会断
      parent.right = node.left
      // 如果删除的节点的左节点不等于前驱,将被删除节点的左节点交给前驱保管，确保被删除节点的左节点不会断
      node.left = delNode.left
    }
    return node
  }

  // 删除通过后继
  removeBySuccessor(key) {
    let parent = this.root
    let current = this.root
    let isLeftNode = false

    while (current.key !== key) {
      parent = current
      if (current.key > key) {
        isLeftNode = true
        current = current.left
      } else {
        isLeftNode = false
        current = current.right
      }
      // 没有找到要删除的
      if (current === null) return false
    }

    // 删除的是叶子节点
    if (current.left === null && current.right === null) {
      if (isLeftNode) {
        parent.left = null
      } else {
        parent.right = null
      }
    }
    // 删除的节点有一个左节点
    else if (current.right === null) {
      if (isLeftNode) {
        parent.left = current.left
      } else {
        parent.right = current.right
      }
    }
    // 删除的节点有一个右节点
    else if (current.left === null) {
      if (isLeftNode) {
        parent.left = current.right
      } else {
        parent.right = current.right
      }
    }
    // 删除的节点有两个子节点
    else {
      const successor = this.getPrecursor(current)
      if (isLeftNode) {
        parent.left = successor
      } else {
        parent.right = successor
      }
      // 将后继节点的左节点连接到删除节点的左节点，确保被删除节点的左节点不会断
      successor.left = current.left
    }
  }

  getSuccessor(delNode) {
    let current = delNode.right
    let node = delNode
    let parent = delNode

    while (current !== null) {
      parent = node
      node = current
      current = current.left
    }

    if (delNode.right !== node) {
      // 如果被删除的节点的右节点不等于后继，将后继节点的右节点交给后继节点的父节点左节点保管，确保后继节点的右节点不会断
      parent.left = node.right
      // 如果被删除的节点的右节点不等于后继，将后继节点的右节点连接到被删除节点的右节点，确保被删除节点的右节点不会断
      node.right = delNode.right
    }
  }
}

let resultStr = ''
const handler = (node) => {
  resultStr += ' ' + node.key + '>' + ' '
}

const bst = new BinarySearchTree()

//2.插入数据
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(19);

// bst.preOrderTraversal(handler)
// bst.midOrderTraversal(handler)
// bst.postOrderTraversal(handler)

// console.log('resultStr', resultStr);

// console.log('max', bst.max());

// console.log('min', bst.min());


// console.log('search', bst.search(18));
// console.log('search2', bst.search(111));


bst.removeByPrecursor(5)
// bst.removeBySuccessor(7)

console.log('删除成功');


bst.preOrderTraversal(handler)

console.log('resultStr', resultStr);



